package com.kehao.leetcode.hard.array;

import org.junit.Test;

public class FirstMissingPositiveSolution {
    public int firstMissingPositive(int[] nums) {
        int result = nums.length+1;
        for (int i = 0; i < nums.length ; i++) {
            if(nums[i]<=0||nums[i]>nums.length){
                nums[i] = nums.length+1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(Math.abs(nums[i])<nums.length+1){
                if(nums[Math.abs(nums[i])-1]>0) {
                    nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0) {
                result=i+1;
                break;
            }
        }
        return result;
    }

    @Test
    public void test01(){
        int[] nums = {1,2,0};
        int result = firstMissingPositive(nums);//3
        System.out.println(result);
    }

    @Test
    public void test02(){
        int[] nums = {3,4,-1,1};
        int result = firstMissingPositive(nums);//2
        System.out.println(result);
    }

    @Test
    public void test03(){
        int[] nums = {7,8,9,11,12};
        int result = firstMissingPositive(nums);//1
        System.out.println(result);
    }

    @Test
    public void test04(){
        int[] nums = {1,2,6,3,5,4};
        int result = firstMissingPositive(nums);//7
        System.out.println(result);
    }

    @Test
    public void test05(){
        int[] nums = {2147483647,100000,1,3,2,4,5,6,7,100001};
        int result = firstMissingPositive(nums);//8
        System.out.println(result);
    }

    @Test
    public void test06(){
        int[] nums = {1,1};
        int result = firstMissingPositive(nums);//2
        System.out.println(result);
    }

}
